#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e5+10;
int n,m;
struct point
{
	int c[2],key,dis,fa;
}p[MAXN];
int getfa(int x)
{
	return p[x].fa==x?x:getfa(p[x].fa);
}
int merge(int a,int b)
{
	if(!a)return b;
	if(!b)return a;
	if(p[a].key<p[b].key)swap(a,b);
	p[a].c[1]=merge(p[a].c[1],b);
	p[p[a].c[1]].fa=a;
	if(p[p[a].c[1]].dis>p[p[a].c[0]].dis)swap(p[a].c[0],p[a].c[1]);
	if(!p[a].c[1])p[a].dis=0;
	else p[a].dis=p[p[a].c[1]].dis+1;
	return a;
}
int del(int x)
{
	p[p[x].c[0]].fa=p[x].c[0];
	p[p[x].c[1]].fa=p[x].c[1];
	int l=p[x].c[0],r=p[x].c[1];
	p[x].dis=p[x].c[0]=p[x].c[1]=0;
	return merge(l,r);
}
int main()
{
	while(scanf("%d",&n)==1)
	{
		memset(p,0,sizeof(p));
		for(int i=1;i<=n;++i)
		{
			scanf("%d",&p[i].key);
			p[i].fa=i;
		}
		scanf("%d",&m);
		for(int i=1;i<=m;++i)
		{
			int x,y;
			scanf("%d%d",&x,&y);
			x=getfa(p[x].fa);y=getfa(p[y].fa);
			if(x==y)
			{
				printf("-1\n");
				continue;
			}
			p[x].key>>=1;p[y].key>>=1;
			x=merge(del(x),x);
			y=merge(del(y),y);
			printf("%d\n",p[merge(x,y)].key);
		}
	}
	return 0;
}